package com.example.question.dp.dp4;

import java.util.Stack;

/**
 * @Date 2023-07-28
 * @Author Jonathan
 */
public class Code04_32 {

    public static void main(String[] args) {
        char s = '('; // 40
        char s1 = ')'; // 41
        System.out.println(s);
        System.out.println(s1);
//        String str = ")()())";
//        String str = ")()())";
        // (((()))
        String str = "()(()";
        Code04_32 code = new Code04_32();

        System.out.println("code.longestValidParentheses(str) = " + code.longestValidParentheses(str));
    }

    /**
     * 双指针解法
     * 双指针对于这种情况:(((()))处理不了
     * 因此需要再从尾到头再遍历一遍
     */
    public int longestValidParentheses(String s) {
        int left = 0, right = 0;
        char[] chars = s.toCharArray();
        int len1 = 0;
        for (char aChar : chars) {
            if (aChar == '(') {
                left++;
            } else {
                right++;
            }
            if (right > left) {
                left = 0;
                right = 0;
            }
            if (left == right) {
                len1 = Math.max(len1, left + right);
            }
        }
        // 从尾到头再遍历一遍即可
        int len2 = 0;
        left = right = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (right < left) {
                left = 0;
                right = 0;
            }
            if (left == right) {
                len2 = Math.max(len2, left + right);
            }
        }
        return Math.max(len1, len2);
    }


    /**
     * 利用栈来解题 时间复杂度和空间复杂度都是O(n)
     * 左括号入栈即可
     * 右括号则弹出一个左括号，先用-1垫底
     * 当右括号遇到没有栈中没有元素的时候  就说明当前有括号后面的子串是一个新的开始
     */
    public int longestValidParentheses3(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int len = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (chars[i] == '(') {
                stack.push(i);
            }
            if (chars[i] == ')') {
                stack.pop();
                if (!stack.isEmpty()) {
                    len = Math.max(len, i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
        }
        return len;
    }


    /**
     * 最长有效括号
     * dp[i] 表示以i字符结尾的最长有效字串的长度
     * "))" i-dp[i-1]-1  ---> dp[i-1]+2 同时 要看以(i-dp[i-1]-2)结尾的情况  其实就是看前一个的情况
     */
    public int longestValidParentheses2(String s) {
        char[] chars = s.toCharArray();
        if (s.length() <= 1) {
            return 0;
        }
        int len = 0;
        int[] dp = new int[chars.length];
        if (chars[0] == '(' && ')' == chars[1]) {
            dp[1] = 2;
            len = 2;
        }
        for (int i = 2; i < chars.length; i++) {
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    dp[i] = 2 + dp[i - 2];
                } else if (chars[i - 1] == ')') {
                    // 处理"))"这种情况
                    if (i - dp[i - 1] - 1 >= 0 && chars[i - dp[i - 1] - 1] == '(') {
                        int pre = (i - dp[i - 1] - 2) >= 0 ? dp[i - dp[i - 1] - 2] : 0;
                        dp[i] = dp[i - 1] + 2 + pre;
                    }
                }
            }
            len = Math.max(len, dp[i]);
        }
        return len;
    }


    public int longestValidParentheses1(String s) {
        return dfs(s.toCharArray(), 0, s.length());
    }

    /**
     * 处理不了这种  ()(())
     */
    private int dfs(char[] chars, int index, int len) {
        if (index >= len) {
            return 0;
        }
        int count = 0;
        // ')' 开头的是不行的
        if (chars[index] == 41) {
            count += dfs(chars, index + 1, len);
        }
        // 正好是能匹配的 '('  ')'
        if (chars[index] == 40 && (index + 1) < chars.length && chars[index + 1] == 41) {
            count = 2 + dfs(chars, index + 2, len);
        }
        // '(' '(' 这种开头的 只能是看下一个
        if (chars[index] == 40 && (index + 1 < chars.length) && chars[index + 1] == 40) {
            count += dfs(chars, index + 1, len);
        }
        return count;

    }
}
